package main

import (
	"fmt"
)

//#link: https://leetcode-cn.com/problems/maximum-ice-cream-bars/
func main() {
	costs := []int{1, 3, 2, 4, 1}
	coins := 7
	fmt.Println(maxIceCream(costs, coins))
}

//计数排序+贪心
func maxIceCream(costs []int, coins int) int {
	result, max := 0, int(1e5)
	//保留当前 价格有几块雪糕
	freq := make([]int, max+1)
	for _, c := range costs {
		freq[c]++
	}

	for i := 1; i <= max && coins >= i; i++ {
		//当前价格可以买的雪糕数和全买此雪糕的数量的最小值
		c := min(freq[i], coins/i)
		result += c
		coins -= c * i
	}
	return result
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
